package 剑指offer;

/*
 *  请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 *	路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
 *	如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
 *  例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
*/
public class _12矩阵中的路径 {
	
	public static void main(String[] args) {
		/*
		 * char [][]bod=new char[][]
		 * {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}; String
		 * word="ABCCED";
		 */
		char [][]bod=new char[][] {{'a'}};
		String word="ab";
		System.out.println(exist(bod,word));
	}
	//dfs(深度优先搜索)回溯法
	 public static boolean exist(char[][] board, String word) {
		 char str[]=word.toCharArray();
		 if(board[0].length==0||board.length==0) {
			return false;
		 }
		 for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if(dfs(board, str, i, j, 0)) return true;
			}
		}
		 return false;
	    }
	 public static boolean dfs(char [][]board ,char []str,int i,int j,int k) {
		 if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=str[k]) return false;
		 if(k==str.length-1) return true;
		 board[i][j]='0';
		 boolean res=dfs(board, str, i+1, j, k+1)||dfs(board, str, i-1, j, k+1)||
				 dfs(board, str, i, j+1, k+1)||dfs(board, str, i, j-1, k+1);
		 board[i][j]=str[k];
		 return res;
	 }
}
